package com.zhaohg.leetcode.easy;

import java.util.Stack;

/**
 * Function: 反向打印链表
 * @author zhaohg
 * Date: 10/02/2018 16:14
 * @since JDK 1.8
 */
public class ReverseNode {
    
    
    /**
     * 利用栈的先进后出特性
     * @param node
     */
    public void reverseNode1(Node node) {
        
        System.out.println("====翻转之前====");
        
        Stack<Node> stack = new Stack<>();
        while (node != null) {
            
            System.out.print(node.value + "===>");
            
            stack.push(node);
            node = node.next;
        }
        
        System.out.println("");
        
        System.out.println("====翻转之后====");
        while (!stack.isEmpty()) {
            System.out.print(stack.pop().value + "===>");
        }
        
    }
    
    
    /**
     * 利用头插法插入链表
     * @param head
     */
    public void reverseNode(Node head) {
        if (head == null) {
            return;
        }
        
        Node node;
        
        Node pre = head;
        Node cur = head.next;
        Node next;
        while (cur != null) {
            next = cur.next;
            
            //链表的头插法
            cur.next = pre;
            pre = cur;
            
            cur = next;
        }
        head.next = null;
        node = pre;
        
        
        while (node != null) {
            System.out.println(node.value);
            node = node.next;
        }
        
    }
    
    
    /**
     * 递归
     * @param node
     */
    public void recNode(Node node) {
        
        if (node == null) {
            return;
        }
        
        if (node.next != null) {
            recNode(node.next);
        }
        System.out.print(node.value + "===>");
    }
    
    
    public static class Node<T> {
        public T       value;
        public Node<T> next;
        
        
        public Node(T value, Node<T> next) {
            this.next = next;
            this.value = value;
        }
    }
}
